package com.dexter.year2023.charpter1_linkedlist.level3.topic3_1环的入口;

import java.util.HashSet;

import com.dexter.year2023.charpter1_linkedlist.level1.Demo1.Node;

import static com.dexter.year2023.charpter1_linkedlist.level3.topic3_1环的入口.Demo1HasCycle.initLinkedListHasCycle;

/**
 * LeetCode 142. 环形链表 II
 * https://leetcode.cn/problems/linked-list-cycle-ii/
 * <p>
 * 给定一个链表的头结点  head ，返回链表开始入环的第一个结点。 如果链表无环，则返回 null。
 * 如果链表中有某个结点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
 * 不允许修改 链表。
 * <p>
 * 示例 1：
 * 输入：head = [3,2,0,-4], pos = 1
 * 输出：返回索引为 1 的链表结点
 * 解释：链表中有一个环，其尾部连接到第二个结点。
 * 示例 2：
 * 输入：head = [1,2], pos = 0
 * 输出：返回索引为 0 的链表结点
 * 解释：链表中有一个环，其尾部连接到第一个结点。
 * 示例 3：
 * 输入：head = [1], pos = -1
 * 输出：返回 null
 * 解释：链表中没有环。
 * <p>
 * 提示：
 * 链表中结点的数目范围在范围 [0, 104] 内
 * -105 <= Node.val <= 105
 * pos 的值为 -1 或者链表中的一个有效索引
 * <p>
 * 进阶：你是否可以使用 O(1) 空间解决此题？
 *
 * @author Dexter
 */
public class Demo2HasCycleFindEntrance {
    /**
     * 判断链表是否有环，且要找到入口
     * <p>
     * LeetCode题目要求，返回索引，但自己在后面做了转换，实际上还是返回Node
     * public ListNode detectCycle(ListNode head){}
     */
    public static void main(String[] args) {
        int[] a = {3, 2, 0, -4};
        int pos = 1;
        // 使用有环方法构造
        Node head = initLinkedListHasCycle(a, pos);
        // 寻找入口
        int testMethod = 2;
        Node entranceNode = null;
        switch (testMethod) {
            case 1:
                // 法1：HashSet去重
                entranceNode = findEntranceByHashSet(head);
                break;
            case 2:
                // 法2：两次双指针
                entranceNode = findEntranceByTwoPoints2(head);
                break;
            default:
                System.out.println("测试方法超出范围");
                break;
        }
        System.out.println(entranceNode.val);
    }

    /**
     * 法1：用HashSet，遇到已存的结点就是入口
     *
     * @param head
     * @return
     */
    private static Node findEntranceByHashSet(Node head) {
        // 初始化
        Node cur = head;
        HashSet<Node> set = new HashSet<>();
        while (cur != null) {
            if (!set.add(cur)) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    /**
     * 法2：双指针【使用两次，找入口】
     *
     * @param head
     * @return
     */
    private static Node findEntranceByTwoPoints2(Node head) {
        if (head == null) {
            return null;
        }
        Node slow = head, fast = head;
        while (fast != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                // 到尾结点还没找到
                return null;
            }
            // 相遇位置，确认有环
            if (fast == slow) {
                // fast回到head，再和slow相遇就是入口位置【重点】
                fast = head;
                while (fast != slow) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return fast;
            }
        }
        return null;
    }
}
